/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhongfang
 *
 */
public class LongestWordinDictionary {

	class Node {
		Node[] next = new Node[26];
		boolean isEnd;
		String rString;
	}

	public String longestWord3(String[] words) {
		// 按照长度分组
		HashMap<Integer, ArrayList<String>> len2Words = new HashMap<>();
		for (String string : words) {
			int len = string.length();
			if (!len2Words.containsKey(len)) {
				len2Words.put(len, new ArrayList<>());
			}
			len2Words.get(len).add(string);
		}
		int curLen = 1;
		String res = "";
		while (len2Words.containsKey(curLen)) {

		}
		return res;
	}

	public String longestWord(String[] words) {
		Node root = new Node();
		for (String string : words) {
			Node cur = root;
			for (int i = 0; i < string.length(); i++) {
				int nextIndex = string.charAt(i) - 'a';
				if (cur.next[nextIndex] == null) {
					cur.next[nextIndex] = new Node();
				}
				cur = cur.next[nextIndex];
			}
			cur.isEnd = true;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		root.rString = "";
		String res = null;
		while (!queue.isEmpty()) {
			int size = queue.size();
			boolean firstOfLevel = true;// 每层第一个，层次遍历
			for (int i = 0; i < size; i++) {
				Node cur = queue.poll();
				for (int j = 0; j < cur.next.length; j++) {
					if (cur.next[j] != null && cur.next[j].isEnd) {
						cur.next[j].rString = cur.rString + String.valueOf((char) ('a' + j));
						if (firstOfLevel) {
							res = cur.next[j].rString;
							firstOfLevel = false;
						}
						queue.add(cur.next[j]);
					}
				}
			}
		}
		return res;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LongestWordinDictionary longestWordinDictionary = new LongestWordinDictionary();
		String[] words = { "a", "banana", "app", "appl", "ap", "apply", "apple" };
		System.out.println(longestWordinDictionary.longestWord(words));
	}

}
